import org.w3c.dom.html.HTMLBRElement;

import javax.sound.sampled.Line;
import java.awt.*;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-06-12
 * Time: 22:34
 */

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}

public class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        Node cur = root;
        while (cur != null) {
            // 遍历每一层
            // 每层首部添加一个哨兵位节点, 使得代码更简洁
            Node head = new Node(-1);
            Node prev = head;
            while (cur != null) {
                // 遍历每一个节点
                if (cur.left != null) {
                    prev.next = cur.left;
                    prev = prev.next;
                }
                if (cur.right != null) {
                    prev.next = cur.right;
                    prev = prev.next;
                }
                // 处理该层节点的下一个节点, 这里注意, 我们已经将上面每层的节点都连接起来了
                cur = cur.next;
            }
            cur = head.next;
        }
        return root;
    }
}
